// https://leetcode-cn.com/problems/combination-sum/
// 39. 组合总和
// 给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出
// candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表返回。
// 你可以按任意顺序返回这些组合。
// candidates 中的同一个数字可以无限制重复被选取。

function combinationSum(candidates: number[], target: number): number[][] {
    const result: number[][] = [];

    function dfs(target: number, combine: number[], idx: number): void {
        if (idx === candidates.length) return;
        if (target === 0) {
            result.push(combine);
            return;
        }

        dfs(target, combine, idx + 1);
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], combine.concat(candidates[idx]), idx);
        }
    }
    dfs(target, [], 0);

    return result;
}
